package com.zyk.leetcode;

/**
 *
 * https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
 *
 * @author zhangsan
 * @date 2021/4/5 17:20
 */
public class J62 {

    public static class Node {
        int v;
        Node next;
        public Node(int v) {
            this.v = v;
        }
    }

    // https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/*
    public static int lastRemaining(int n, int m) {
        if(n < 2) {
            return 0;
        }
        if(m == 1) {
            return n-1;
        }
        Node root = generateRing(n);
        while (root.next != root) {
            int i = 2;
            while (i < m) {
                root= root.next;
                i++;
            }
            root.next = root.next.next;
            root = root.next;
        }
        return root.v;
    }

    public static Node generateRing(int n) {
        Node root = new Node(0);
        Node cur = root;
        for (int i = 1; i < n; i++) {
            cur.next = new Node(i);
            cur = cur.next;
        }
        cur.next = root;
        return root;
    }


    // for test
    public static void main(String[] args) {
        int n = 5, m = 1;
        System.out.println(lastRemaining(n, m));
    }
}
